#!/usr/bin/env python
# encoding: utf-8

import sys
import os
import random
import networkx as nx

"""
'
' Author: Jonathan Potter
'
' Name: Utilities
'
' Description: Defines methods used by all protocols
' 		
' Parameters: None
'
"""
class Utilities:
	
		
	"""
	'
	' Name: pairs
	'
	' Description: Pairs up items of a list
	' 		
	' Parameters: a A list
	'
	' Returns: A list of pairs
	'
	"""
	@staticmethod
	def pairs(a):
		return zip(*[a[x:] + a[:x] for x in range(2)])
	
	
	"""
	'
	' Name: pathTime
	'
	' Description: Calculates and return time data will take to traverse given path
	' 		
	' Parameters: parameters, network, path, nodeDelay
	'
	' Returns: Time in milliseconds
	'
	"""
	# Returns the total time in milliseconds.  nodeDelay must be given in milliseconds!
	@staticmethod
	def pathTime(parameters, network, path, nodeDelay):
		numberOfPackets = parameters['defaultDataNumberOfPackets']
		packetSize = parameters['packetSize']
		
		pairs = Utilities.pairs(path)[:-1]
		
		# 125000 = (10 ** 3) / 8 to convert Mb/s to B/ms
		#print "PathA: ", path
		extractNormilizedBW = lambda (u, v): Utilities.getBandwidth(parameters, network, u, v) * 125000
		bandwidths = map(extractNormilizedBW, pairs)
		wireTimes = map(lambda bw: float(packetSize)/bw, bandwidths)
		
		onePacket = nodeDelay * len(path) + sum(wireTimes)
		bottleNeck = max(nodeDelay, *wireTimes)
		
		# In ms
		totalTime = onePacket + (bottleNeck * (numberOfPackets - 1))
		
		# In ms
		return totalTime
	
	
	"""
	'
	' Name: getBandwidth
	'
	' Description: Calculates and return total bandwidth along given path
	' 		
	' Parameters: parameters, network, node1, node2 
	'
	' Returns: Bandwidth in bits/second
	'
	"""
	@staticmethod
	def getBandwidth(parameters, network, u, v):
		(minWeight, maxWeight) = parameters['bandwidthRange']
		weight = network[u][v]['weight']
		
		bandwidth = (maxWeight - weight) + minWeight
		
		return bandwidth

"""
'
' Author: Jonathan Potter
'
' Name: Simple
'
' Description: Implements Simple Protocol
' 		
' Parameters: None
'
"""
class Simple:

	"""
	'
	' Name: Constructor
	'
	"""	
	def __init__(self):
		pass
		
	"""
	'
	' Name: getPath
	'
	' Description: Finds shortest path thru network using dijkstra's algorithm 
	' 		
	' Parameters: self, network, parameters, source, destination
	'
	' Returns: path
	'
	"""		
	def getPath(self, network, parameters, source, destination):
		return nx.dijkstra_path(network, source, destination)
	
	"""
	'
	' Name: runSimulation
	'
	' Description: Runs simulation of protocol
	' 		
	' Parameters: self, network, parameters, path
	'
	' Returns: runtime of protocol on given path
	'
	"""
	def runSimulation(self, network, parameters, path):
		hopTime = random.uniform(*parameters['hopTimeRange'])
		return Utilities.pathTime(parameters, network, path, hopTime)


"""
'
' Author: Doug
'
' Name: Crowds
'
' Description: Implements Crowds Protocol
' 		
' Parameters: None
'
"""
class Crowds:
	"""
	'
	' Name: Constructor
	'
	"""
	def __init__(self):
		pass

	"""
	'
	' Name: getPath
	'
	' Description: Using crowds to find the path. Uses Dijkstra's shortest path to find 
		       the path from the last jondo to the destination.
	'
	' Parameters: self, network, parameter, src
	'
	' Returns: The path.
	'
	"""
	def getPath(self, network, parameters, src):
		myNetwork = network.copy()

		temp = network.copy()
		temp.remove_node(src)
		u = random.choice(temp.nodes())

		dest = myNetwork.number_of_nodes()
		next = src
		crowdsPath = [next]

		while True:
			next = self.getNext(myNetwork, next)
			crowdsPath.append(next)

			if self.flipBiasedCoin() == 1:
				break

		dest = myNetwork.number_of_nodes()
		myNetwork.add_node(dest)
		myNetwork.add_edge(u, dest, weight = random.randint(*parameters['bandwidthRange']))

		shortestPath = nx.dijkstra_path(myNetwork, next, dest)

		return (crowdsPath, shortestPath, myNetwork)

	"""
	'
	' Name: getNext
	'
	' Description: Gets the next random jondo.
	'
	' Parameters: self, network, src
	'
	' Returns: The next hop.
	'
	"""
	def getNext(self, network, src):
		neighbors = network.neighbors(src)
		next = neighbors[random.randint(0, len(neighbors) - 1)]
		return next

	"""
	'
	' Name: flipBiasedCoin
	'
	' Description: Flips a coin that is biased torwards heads.
	'
	' Parameters: self
	'
	' Returns: True if heads, false if tails.
	'
	"""
	def flipBiasedCoin(self):
		heads = 0.6
		tails = 1 - heads
		flip = random.random()

		if flip > tails:
			return 1
		else:
			return 0

	"""
	'
	' Name: runSimulation
	'
	' Description: Runs simulation of the protocol.
	'
	' Parameters: self, network, parameters, crowdsPath, shortestPath
	'
	' Returns: Runtime of protocol on given path.
	'
	"""
	def runSimulation(self, network, parameters, crowdsPath, shortestPath):
		encryptTime = 2 * random.uniform(*parameters['encryptionTimeRange'])
		hopTime = random.uniform(*parameters['hopTimeRange'])
		t1 = Utilities.pathTime(parameters, network, crowdsPath, encryptTime + hopTime)
		t2 = Utilities.pathTime(parameters, network, shortestPath, hopTime)
		return t1 + t2

	"""
	'
	' Name: merge
	'
	' Description: Merges two lists.
	'
	' Parameters: self, l1, l2
	'
	' Returns: N/A
	'
	"""
	def merge(self, l1, l2):
		l2.pop(0)
		l1.extend(l2)
		
"""
'
' Author: Erin
'
' Name: OnionRouting
'
' Description: Implements Onion Routing Protocol
' 		
' Parameters: None
'
"""

class OnionRouting:
	"""
	" Using Original instead of RTT for initial tests to choose path
	"""
	
	#constructor
	"""
	'
	' Name: Constructor
	'
	"""
	def __init__(self):
		pass
		
	"""
	'
	' Name: runSimulation
	'
	' Description: Runs simulation of protocol
	' 		
	' Parameters: self, network, parameters, path
	'
	' Returns: runtime of protocol on given path
	'
	"""
	def runSimulation(self, network, parameters, path):
		nodeDelay = random.uniform(*parameters['hopTimeRange'])
		runTime = self.returnOverhead(parameters, network, path, nodeDelay)
		return runTime
		
	"""
	'
	' Name: getPath
	'
	' Description: Chooses a random path through graph
	' based on the way Tor uses the OR protocol
	' random nodes are chosen, and then connected in an
	' efficient manner
	' 		
	' Parameters: self, parameters, ORgraph, source, destination
	'
	' Returns: path
	'
	"""		
	def getPath(self, parameters, ORgraph, source, destination):
		# Get a random path, within a reasonable length
		myLength = 3 #this is the path length used by Tor
		next = source
		path = []
		nodes = ORgraph.nodes()
		nodes.remove(source)

		
		for i in range(0 , myLength - 1):
			#choose a random node
			nextTemp = random.choice(nodes)
			#now remove it from the list of nodes so it won't come up again
			nodes.remove(nextTemp)
			#node must not be destination
			if nextTemp != destination:
				#add shortest path from random node to next random node using dijkstra's alg
				path = path + nx.dijkstra_path(ORgraph, next, nextTemp)
				#pop off last element so there won't be repeats
				path.pop()
				next = nextTemp
			else:
				i+=1 #otherwise do another loop in graph
				
		#add final dijkstra's path from last random node to dest
		path = path + nx.dijkstra_path(ORgraph, next, destination)
			
		return path
		
		
	"""
	" return parameters
	" Return measurements for final statistics
	"""	
	
	
	"""
	'
	' Name: returnOverhead
	'
	' Description: Calculates and returns runtime of protocol thru path
	' 		
	' Parameters:self, parameters, network, path, nodeDelay
	'
	' Returns: runtime
	'
	"""	
	def returnOverhead(self, parameters, network, path, nodeDelay):
		#calculate and return overhead, incl. encryption time
		encryptPerPacket = random.uniform(*parameters['encryptionTimeRange'])
		
	 	transmitTime = Utilities.pathTime(parameters, network, path, nodeDelay)
	 	encryptTime = Utilities.pathTime(parameters, network, path, encryptPerPacket)
	 	#double encrypt time to account for encrypt and decrypt
		myTime = 2*encryptTime + transmitTime
		return myTime
